iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 7
0
Modern Web

30天每日死磕面试题3+1系列 第 7

DAY 7 不用运算符算出两数之和?

  • 分享至 

  • xImage
  •  

题目:

你一共有 n 枚硬币,你需要将它们摆成一个阶梯形状,第 k 行就必须有 k 枚硬币。

给定一个数字 n ,找出可形成完整阶梯行的总行数。
n 是一个非负整数,并且在32位有符号整形范围内。
示例:
① n=5
硬币排列成:

● ●
● ●
因为第三行不完整,所以 return 2 .
② n=8
硬币的排列为:

● ●
● ● ●
● ●
所以返回值为 3.

解题

code:

var arrangeCoins = function(n) {
let k =0;
while (n>0) {
    k++;
    n=n-k;
}
return n === 0? k:k-1;
};

执行测试后发现是没问题的。
这一种办法就是暴力破解法,思路是这样的:
设置 k 为行数,循环n ,直到n 小于或者等于0 为之,
每次循环k+1,同时 n-k(因为行数=硬币数),
最后看n是否为0,如果是刚刚好,返回k,如果不是0,即最后一行是失效的,所以返回k-1.
但是我们还可以用二分查找法来实现这个算法.
涉及知识点
用Math的方法(我在前面的面试题目中,有介绍过,可以看一下).
然后我们需要掺杂数学知识:
计算第k行的结果公式为 : k*(k+1) /2

code:

var arrangeCoins =function {
    if (!n) {
    return 0;
    }
    let sum = n*2
    let left = 0;
    let right = n;
    while(n) {
        let middle = Math.round((left+right)/2);
        if(middle *(middle+1) ===sum) {
            return middle;
        } else if (middle * (middle+1) < sum) {
            left= middle;
        } else {
            right=middle;
        }
        if(left=== right-1) {
            return left;
        }
    }
};

以上,就是二分法查找的方法求解。
那么,我前面提到的不用 + - 的符号可以做到两个整数的和是如何做到的呢, 下面 ,就让我们来看一下吧。
涉及知识点 : 异或
这个知识点是不能很快的了解,所以希望大家可以自己去搜索资料,我就直接贴code了

var getSum = function(a,b) {
    if (a === 0 ) return b;
    if (b === 0) return a;
    return getSum(a^b,(a&b) <<1);
}

代码块很少,但是知识点并不简单。
以上题目来自力扣(LeetCode) https://leetcode-cn.com
下面,就是今天的前端面试题了,不过我在前面说过,以后的话就是第二天公布我自己的参考答案,所以今天自己可以去网路上面搜寻,并且在下方留言你的看法或者建议。

HTML

input的onblur和onchange事件区别是什么?

CSS

什么是脱离文档流?有什么办法可以让元素脱离标准的文档流?

JS

请使用原生的js实现斐波那契数列


上一篇
DAY 6 :锚点的反复纵跳秘籍?如何实现一个全屏的功能?
下一篇
摩斯密码如何实现?响应式设计和自适应设计的区别在哪里?
系列文
30天每日死磕面试题3+19
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 則留言

1

代數解法

function fibonacci(n) {
 return Math.round(
 (Math.pow((1 + Math.sqrt(5)) / 2, n) - Math.pow((1 - Math.sqrt(5)) / 2, n)) * (Math.sqrt(5) / 5)
 )
}

不使用加減號實現加減法
https://developer.mozilla.org/zh-TW/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators#(%E4%BD%8D%E5%85%83_XOR)
本科系應該都知道二進位加法只需透過AND XOR即可實現
AND結果是進位數 因此使用 << 1 位移進位
XOR結果是未含進位結果
最後再把未含進位結果加上進位如有進位即不為0即繼續加進位 直到為零

想看二進位結果可使用
mynumber.toString(2) (數字轉二進位)
parseInt(mybinary,2) (二進位轉數字)

我要留言

立即登入留言